package com.demo.java.OD101_150.OD101;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【求最大数字】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145662955
 */
public class OdMain {
    // 用于存储所有可能的数字组合结果
    static List<Integer> resList = new ArrayList<>();
    // 用于存储输入的字符
    static List<String> inputStrs = new ArrayList<>();

    /**
     * 判断是否满足子序列的条件
     * @param child 子序列
     * @return 如果是子序列返回true，否则返回false
     */
    public static boolean isChild(List<String> child) {
        int index = 0; // 标记遍历位置
        int count = 0; // 记录匹配的数量
        // 遍历子序列中的每个元素
        for (int i = 0; i < child.size(); i++) {
            String str = child.get(i);
            // 查找每个元素是否存在于输入的字符列表中，并保持顺序
            for (int j = index; j < inputStrs.size(); j++) {
                String temp = inputStrs.get(j);
                if (temp.equals(str)) {
                    index = j + 1; // 记录当前位置的下一个位置
                    count++; // 匹配数量加一
                    break;
                }
                // 如果遍历完所有字符都没有找到匹配的子元素，返回false
                if (j == inputStrs.size() - 1) {
                    return false;
                }
            }
        }
        // 如果匹配的元素个数和子序列的大小一致，返回true
        return count == child.size();
    }

    /**
     * 递归交换字符串并生成所有可能的数字组合
     * @param strs 要排列的字符串
     * @param start 当前要交换的位置
     * @param end 字符串的最后一个位置
     */
    public static void swapAndCombine(List<String> strs, int start, int end) {
        if (start == end) {
            // 当start == end时，表示排列已经完成，生成一个数字字符串
            String numStr = String.join("", strs);
            // 如果这个数字组合未出现过且是一个合法子序列，就加入结果列表
            if (!resList.contains(Integer.parseInt(numStr)) && isChild(strs)) {
                resList.add(Integer.parseInt(numStr));
            }
        } else {
            // 从start到end的位置进行交换
            for (int i = start; i < strs.size(); i++) {
                // 如果当前字符串已经和前一个字符串相同，跳过
                if (i != start && strs.get(i).equals(strs.get(start))) {
                    continue;
                }
                // 交换字符
                Collections.swap(strs, i, start);
                // 如果交换后的第一位是0，则跳过（避免数字开头为0的情况）
                if (strs.get(0).equals("0")) {
                    continue;
                }
                // 递归交换下一个位置
                swapAndCombine(strs, start + 1, end);
                // 交换回去，回溯
                Collections.swap(strs, i, start);
            }
        }
    }

    /**
     * 主方法，程序入口
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        // 创建一个Scanner对象，用于读取用户输入
        Scanner sc = new Scanner(System.in);
        // 读取输入的数字字符串
        String inputStrsStr = sc.nextLine();
        // 将输入的每个字符逐个加入到inputStrs列表中
        for (int i = 0; i < inputStrsStr.length(); i++) {
            String inputStr = String.valueOf(inputStrsStr.charAt(i));
            inputStrs.add(inputStr);
        }

        // 使用map统计每个字符的出现次数
        Map<String, Integer> map = new HashMap<>();
        for (String inputStr : inputStrs) {
            map.put(inputStr, map.getOrDefault(inputStr, 0) + 1);
        }

        // 创建一个新的列表，存储每个字符和其出现次数
        List<String> lis = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String num = entry.getKey();
            lis.add(num); // 每个字符添加一次
            // 如果某个字符出现次数大于等于2，则添加两次，允许重复使用
            if (entry.getValue() >= 2) {
                lis.add(num);
            }
        }

        // 递归地生成所有可能的数字组合
        swapAndCombine(lis, 0, lis.size() - 1);

        // 将结果列表按升序排列
        Collections.sort(resList);

        // 输出最大的数字
        System.out.println(resList.get(resList.size() - 1));
    }
}